package offer.tree;

/**
 * @author DengYuan2
 * @create 2021-02-28 19:36
 */
public class n_33 {
    public static void main(String[] args) {
        n_33 n = new n_33();
        int[] arr={4,8,6,12,16,14,10};
        boolean res = n.VerifySquenceOfBST(arr);
        System.out.println(res);
    }

    /**
     * 思想：根节点的左子树都小于它，右子树都大于它
     * @param sequence
     * @return
     */
    public boolean VerifySquenceOfBST(int [] sequence) {
        if (sequence==null || sequence.length==0){
            return false;
        }
        return helper(sequence,0,sequence.length-1);

    }

    public boolean helper(int[] arr,int start,int end){
        if (end<=start+1){
            return true;
        }
        int subRoot=arr[end];
        int cur=start;
        //找到第一个大于subRoot的值
        while (cur<end && arr[cur]<=subRoot){
            cur++;
        }
        //如果true，此时cur为右子树的第一个
        for (int i = cur; i < end; i++) {
            if (arr[i]<subRoot){
                return false;
            }
        }
        return helper(arr,start,cur-1)&&helper(arr,cur,end-1);

    }

    public boolean VerifySquenceOfBST2(int [] sequence) {
        if (sequence==null||sequence.length==0){
            return false;
        }
        return getResult(sequence,0,sequence.length-1);
    }

    public boolean getResult(int[] arr,int start,int end){
        if (start<end){
            int last=arr[end];
            int idx=start;
            //找到第一个大于last的数
            while (idx<end&&arr[idx]<last){
                idx++;
            }

            for (int i = idx; i < end; i++) {
                if (arr[i]<last){
                    return false;
                }
            }

            return getResult(arr,start,idx-1)&&getResult(arr,idx,end-1);

        }
        return true;
    }
}
